\documentclass[compressed,narroweqnarray,inline]{ieee}
%\documentclass[%
%	%draft,
%	%submission,
%	%compressed,
%	final,
%	%
%	%technote,
%	%internal,
%	%submitted,
%	%inpress,
%	reprint,
%	%
%	%titlepage,
%	notitlepage,
%	%anonymous,
%	narroweqnarray,
%	inline
%	%twoside
%	]{ieee}

\usepackage{ieeefig}
\usepackage{listings}
\usepackage{pdfcolmk}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{float}
\usepackage{subfig}
\usepackage{verbatim}
\usepackage{wrapfig}
\usepackage{moreverb}
\usepackage{fancyhdr}
\usepackage{xcolor}
\usepackage{color}
\usepackage{url}

\usepackage{multicol}
\linespread{1.3} % 1.5 line spacing


\newenvironment{changemargin}[2]{%
\begin{list}{}{%
%\setlength{\topsep}{0pt}%
\setlength{\leftmargin}{#1}%
\setlength{\rightmargin}{#2}%
%\setlength{\listparindent}{\parindent}%
%\setlength{\itemindent}{\parindent}%
%\setlength{\parsep}{\parskip}%
}%
\item[]}{\end{list}}


\begin{document}

%----------------------------------------------------------------------
% Title Information, Abstract and Keywords
%----------------------------------------------------------------------
\title[Data Types in Common Lisp]{%
       An Overview of Data Types and Structures in the Common Lisp Programming Language}

% format author this way for journal articles.
\author[SHORT NAMES]{%
      Anthony Naddeo\member{Student Member}
      \authorinfo{%
      A. Computer Science Undergraduate Student,
      University of Maine, Orono ME 04469, USA,
      Phone: \mbox{(347) 210-0185}, email: \mbox{anthony.naddeo@gmail.com}}
  }

% format author this way for conference proceedings
\author[SHORT NAMES]{%
      Anthony Naddeo\member{Fellow}
      \authorinfo{%
      Computer Science Undergraduate Student\\
      University of Maine, Orono ME 04469, USA\\
      Phone: (347) 210-0185, email: anthony.naddeo@gmail.com}
  }

% specifiy the journal name
\journal{COS 301, 2011}

% Or, specify the conference place and date.
%\confplacedate{Ottawa, Canada, May 19--21, 1997}

% make the title
\maketitle   
\thispagestyle{empty}     
\newpage

\begin{abstract}  
This paper examines the various control flow structures and error handling procedures in the Common Lisp programming language. This opportunity is being used to expose the extensible and expressive macro system that Common Lisp posses, as it enables the existence of many constructs in the language, as well as the creation of any construct not in the language.
\end{abstract}

% do the keywords
\begin{keywords}
Lisp, control flow, types, Common Lisp, macros, error handling, customization
\end{keywords}

%config the listings settings
\lstset{language=Lisp,
identifierstyle=\ttfamily,
breaklines=true,
tabsize=2,
%title=\lstname,
basicstyle=\footnotesize,
keywordstyle=\color[rgb]{0.5,0.5,0},
commentstyle=\color{red},
stringstyle=\color[rgb]{0,0.5,0}}

\pagenumbering{roman}
\newpage

\tableofcontents
\newpage
\pagenumbering{arabic}
 
\begin{multicols}{2}
%----------------------------------------------------------------------
% SECTION I: Introduction
%----------------------------------------------------------------------
\section{Introduction}\label{sec:intro}
\PARstart Common Lisp's robust control flow constructs in combination with its expressive macro system give programmers the ability to create any type of control flow within their programs. The built in constructs commonly found in other languages cease to be a limited selection of control layouts and instead become building blocks for expressive and concise loops and conditional statements. 

The following sections examine what exactly these constructs are and how to expand off of them for fine tuned control. 

%----------------------------------------------------------------------
% SECTION X: Control Structures and Flow
%----------------------------------------------------------------------
\section{Control Structures and Flow}\label{sec:control}

The term control structure is somewhat vague, but generally refers to some structure that allows programmers to control the execution of code within a program. The Wikipedia page on control flow provides a summarization of the different types of control flow statements that exist in languages\cite{wiki_control}.

\begin{itemize}
\item continuation at a different statement
\item executing a set of statements only if some condition is met
\item executing a set of statements zero or more times, until some condition is met
\item executing a set of distant statements, after which the flow of control usually returns 
\item stopping the program, preventing any further execution
\end{itemize}

Discussing control structures in Common Lisp is much like discussing data types; there are a great number of options and very lose boundaries on what exactly is built into the language. This complication is mostly due to the powerful macro system discussed in Section \ref{sec:macro}. The following sections will examine what facilities Common Lisp offers for controlling the flow of program execution, despite most of them being macros that are built off of one another.

%----------------------------------------------------------------------
\subsection{Unconditional Jumps}

The simplest implementation of control flow (arguably the naive approach to control flow) is the \textit{goto} statement. Common Lisp uses \texttt{tagbody} and \texttt{go} to implement this functionality.

\begin{figure}[H]
\begin{lstlisting}
(tagbody
   (go tag2)
   tag1
   (print "This is tag1")
   tag2
   (print "This is tag2"))
   
=> "This is tag2"
\end{lstlisting}
\caption{Common Lisp goto}
\label{fig:goto1}
\end{figure}

The \texttt{tagbody} operator sets up a new lexical scope in which a series of tags and forms are declared. Within this body, \texttt{go} can be called to jump to a specific tag; \texttt{tag2} is jumped to in figure \ref{fig:goto1}. 

\texttt{go} and \texttt{tagbody} are not particularly powerful or expressive but they are the foundation to many more complex structures in Common Lisp. 



% control flow neccesary to work around functions with side effects
% ie. prog1 and prog2 \cite{cl_api_prog}


%----------------------------------------------------------------------
\subsection{Simple Iteration Constructs}

The \texttt{dolist} and \texttt{dotimes} macros are specialized forms of the \texttt{do} macro that exist to cater to common use patterns. All of these macros are implicit \texttt{tagbody}s as well, enabling the use of \texttt{go} within their body. As their names may imply, they enable programmers to iterate over lists or through ranges of integers without having to use more complex control structures.


\begin{figure}[H]
\begin{lstlisting}
(dolist (element `(1 2 3 4 5) 
        (print "Done!"))
  (print element))
  
=> 1 
2 
3 
4 
5 
"Done!"
\end{lstlisting}
\caption{The \texttt{dolist} Macro}
\label{fig:dolist}
\end{figure}

The \texttt{dolist} function takes a variable and a list to iterate over, followed by an optional form to be executed upon completion and a series of zero or more tags or forms.

As mentioned, the \texttt{dotimes} macro operates in a similar fashion, but iterates over integers instead of lists. This accomplishes what simple, count controlled \textit{for} loops accomplish in languages like C and Java. 

\begin{figure}[H]
\begin{lstlisting}
(dotimes (var 5)
  (print var))

=> 0
1
2
3
4
\end{lstlisting}
\caption{The \texttt{dotimes} Macro}
\label{fig:dotimes}
\end{figure}

The \texttt{dotimes} function is semantically similar to \texttt{dolist}, but replaces the list with an integer form; 5 in the case of Figure \ref{fig:dotimes}.

These are both fine for specific use cases, but often times a macro with greater potential is needed. 


%----------------------------------------------------------------------
\subsection{The \texttt{loop} and \texttt{do} Macros}

\texttt{loop} and \texttt{do} serve as more full featured looping and iterating constructs. They can do almost anything  a programmer would need but they can be overwhelming outside of normal use cases. A simple example of \texttt{loop} is a direct rewrite of the code in Figure \ref{fig:dolist} and Figure \ref{fig:dotimes}.

\begin{figure}[H]
\begin{lstlisting}
; translated dolist
(loop for x in `(1 2 3 4 5) do
     (print x))
=> 1 
2 
3 
4 
5 

;translated dotimes
(loop for x from 1 to 5 do
     (print x))
=> 1 
2 
3 
4 
5
\end{lstlisting}
\caption{\texttt{loop}}
\label{fig:loop}
\end{figure}

An immediate observation is the odd syntax; \texttt{loop} appears to have keywords built into the argument list. This is possible because of the macro system and allows for loops behavior to be directed by sets of clauses. This particular \textit{for} clause will seem familiar to Python programmers. Reference the Common Lisp Hyper Spec to view the lengthy list of possible clauses that control the looping behavior\cite{cl_api_loop}.

The \texttt{do} macro has a more Lisp-like, straight forward form than \texttt{loop} does. 

\begin{figure}[H]
\begin{lstlisting}
(do ( (x 0 (+ 1 x)) (y 3 (- y 1)) )
    ((eql x 3) ;end test form                                                   
     (print "done")) ;result form                                               
  (print x)  ;body                                                              
  (print y))
  
=> 0 
3 
1 
2 
2 
1 
"done"
\end{lstlisting}
\caption{\texttt{do}}
\label{fig:do}
\end{figure}

The comments next to each line attempt to clarify the semantics. The first form is a list of variable declarations of the form \texttt{(var (init-value) (step-value))}, where \texttt{step-value} refers to some form that is used to assign a value to \texttt{var} after each iteration. The second form is a condition that ends the looping. The third form is executed upon completion and the remaining forms compose the body of the loop, executed every iteration. 

The \texttt{do} loop is a more consistent construct than \texttt{loop} and it does not require programmers to have a list of possible special form clauses on hand to use it. In fact, the macro-expanded version of \texttt{do} (discussed in Section \ref{sec:macro}) represents a series of \texttt{go} operators in a \texttt{tagbody}, with assignments occurring at the bottom of the body.

\begin{figure}[H]
\begin{lstlisting}
(BLOCK NIL
 (LET ((X 0) (Y 3))
  (TAGBODY #:LOOP-9519  ; setup tagbody 
    (IF (EQL X 3) (GO #:END-9520)) 
      (PRINT X) (PRINT Y) ;loop body
   (PSETQ X (+ 1 X) 
     Y (- Y 1))  ;update vars
     (GO #:LOOP-9519) #:END-9520 ;loop
   (RETURN-FROM NIL (PROGN (PRINT "done"))))))
\end{lstlisting}
\caption{What \texttt{do} Actually Represents}
\label{fig:expanded-do}
\end{figure}

This examples alludes to the actual source of the expressive power of \texttt{do} and \texttt{loop} as well as their drastically different forms: macros. 

%----------------------------------------------------------------------
% SECTION X: Macros
%----------------------------------------------------------------------
\section{Macros}\label{sec:macro}

%The Common Lisp macro system is a unique facility that allows programmers to create extremely expressive and complex programs encapsulated within simple, specific forms. Many of the control structures in Common Lisp are defined as macros that expand into large portions of custom code. Refer to the appendix, section \ref{sec:macro-expand} for an example of what a \texttt{loop} macro actually represents when it is expanded using the \texttt{macroexpand} function. 



The discussion of control flow in other languages is likely to include the semantics of a handful of different looping structures and conditional statements; Common Lisp goes one step further with its powerful macro system. 

A macro in Common Lisp is a function that acts on programs (lists) themselves, as opposed to what those programs represent\cite{common_lisp_macro}. Like macros in C, they are evaluated before runtime. Unlike macros in C, they are a fundamental part of the language and their use is not restricted to including other files and testing for variable definitions. 

Most programmers have come to expect some type of \textit{for} loop in a language they are learning. While Common Lisp does offer its own looping facilities, none of them translate directly into a Java or C \textit{for} loop. This problem can be solved using macros. 

\begin{figure}[H]
\begin{lstlisting}
(defmacro for (dec-form
               test-form
               inc-form
               &rest rest)

  ;; allow one set of parenthesis to be used                                    
  ;; if only one variable needs to be declared                                  
  (if (not (listp (car dec-form)))
      (setf dec-form (list dec-form)))

  `(let ,dec-form
     (tagbody
      start-tag
        (if ,test-form
            (progn
              ,@rest
              (setf ,(caar dec-form) ,inc-form)
              (go start-tag))))))


\end{lstlisting}
\caption{Creating the \textit{for} Loop}
\label{fig:for}
\end{figure}

Using this macro, expressions can be written as follows.

\begin{figure}[H]
\begin{lstlisting}
(for (i 0) (< i 10) (+ i 1)
  (print i))
\end{lstlisting}
\caption{Custom \textit{for} loop}
\label{fig:forcode}
\end{figure}

The first form in the \texttt{for} loop declares a new variable binding. The second form establishes the looping test that is evaluated at the start of each loop and the third form updates the value of the declared variable. Finally, the \texttt{\&rest} is how Common Lisp specifies a variable amount of arguments. In this case, these arguments serve as the body of the \texttt{for} loop. This is not quite as flexible as a real \textit{for} loop in C, but servers to show that one can potentially be created.

This macro expands into the form described within Figure \ref{fig:for}. This can be seen by calling the \texttt{macroexpand} function.

\begin{figure}[H]
\begin{lstlisting}
(LET ((I 0))
 (TAGBODY START-TAG
  (IF (< I 10) 
      (PROGN (PRINT I) 
             (SETF I (+ I 1)) 
             (GO START-TAG)))))
\end{lstlisting}
\caption{Expanded \texttt{for} Macro}
\label{fig:expand}
\end{figure}

Notice the absence of the first \texttt{if} statement in the expanded macro.  This is because that \texttt{if} statement was evaluated during macro expansion to modify the form that the macro should return. Specifically, it tailored the input to the \texttt{let} operator to allow input of the form \texttt{(var 0)} instead of requiring an additional set or parenthesis, \texttt{((var 0))}. Everything else in the macro definition was back quoted, and thus not evaluated. 

The commas in the macro definition are to override the back quote and evaluate only certain sub forms, like variable names. Without the commas, the various argument forms would remain variable names (i.e. test-form, inc-form) and then throw an error for being undefined at runtime. 

It is easy to see how simple interfaces to complex programs can be created using macros. If no built in control structures lend themselves to a particular problem then a new one can be created, building on top of existing functions and macros. This is drastically different from languages like Python that cannot even implement their own \textit{for} loops in themselves. Peter Seibel described macros best in his Practical Common Lisp Google Talk\cite{seibel_video}:

\noindent \textit{``Macros let me have what I say, mean what I want.''}


%----------------------------------------------------------------------
% SECTION X: Exception Handling 
%----------------------------------------------------------------------
\section{Exception Handling}\label{sec:error}

Steele describes what errors mean to Common Lisp in his specification\cite{common_lisp_error}. \\

\noindent \textit{Conceptually, signaling an error in a program is an admission by that program that it does not know how to continue and requires external intervention. Once an error is signaled, any decision about how to continue must come from the ``outside.''} \\

In addition to his description, he divides \textit{errors} into four general categories\cite{common_lisp_error_types}. 

\begin{itemize}
\item \textbf{Warnings.} Display command line warnings that do not interrupt program execution.
\item \textbf{Fatal Errors.} Errors that cannot be returned from.
\item \textbf{Continuable Errors.} Errors that can be fixed through user interaction or some default options that programmers set up.
\item \textbf{Breaks.} Used for setting debugging breakpoints in code.
\end{itemize}

\begin{figure}[H]
\begin{lstlisting}
 (defun ++ (n)
   (if (not (typep n `integer))
       (error "n must be an integer"))
   (+ n 1))

 (print (++ 3))
=> 4

 (print (++ `f))
=> *** - n must be an integer
\end{lstlisting}
\caption{Signaling Fatal Errors}
\label{fig:error}
\end{figure}

The \texttt{error} function is used to signal fatal errors and deliver useful debugging information. The example in Figure \ref{fig:error} uses error as a form of type checking. 

Signaling fatal errors are appropriate in many situations, but functions like \texttt{cerror} enable programmers to trigger \textit{continuable errors} that allow error correction. 

\begin{figure}[H]
\begin{lstlisting}
(defun ++ (n)
  (if (not (typep n `integer))
      (progn 
        (cerror "return 0 instead" "~s was
        passed to function inc, should have been 
        an integer." n)
             0)
      (+ n 1)))


(print (++ 3))
=> 4

(print (inc `f))
=> ** - Continuable Error

F was passed to function inc, should have been an integer.
If you continue (by typing 'continue'): return 0 instead
The following restarts are also available:

SKIP    :R1      skip (PRINT #)
STOP    :R2      stop loading file
ABORT   :R3      Abort main loop
Break 1 [2]> continue
0

(print `Finished)
=> FINISHED
\end{lstlisting}
\caption{Signaling a Continuable Error}
\label{fig:continue}
\end{figure}

The structure of the code in Figure \ref{fig:continue} was changed to place \texttt{(+ n 1)} in the \textit{else} portion of the conditional block to ensure a fatal error was not called by the \texttt{+} function if the user chose to continue without changing the incorrect input. The dialog is implementation dependent.

Breaks operate in a similar fashion but does not allow any error correcting behavior to take place before dropping back to the debugging options. It is meant to be a debugging tool, rather than an error signaling function.

A continuable error that does not offer any correction and is not at risk of causing a fatal error later in the program may as well be implemented as a warning with the \texttt{warn} function.

\begin{figure}[H]
\begin{lstlisting}
(defun ++ (n)
  (if (not (typep n `integer))
      (warn "n was supposed to be an integer")
      (+ 1 n)))

(print (++ 3))
=> 4

(print (++ `f))
=>WARNING: n was supposed to be an integer
NIL
\end{lstlisting}
\caption{Signaling a Warning}
\label{fig:warn}
\end{figure}

The warning is simply output to to standard out without interrupting execution. 

These samples serve as representative examples for the error system in Common Lisp. From here, more complex error correction can be obtained by combining conditions with the macro system. 

%----------------------------------------------------------------------
% SECTION X: Conclusion
%----------------------------------------------------------------------
\section{Conclusion}\label{sec:conc}

Common Lisp's strength lies in its customization and extensibility, allowing programmers to do everything from creating custom macros that abstract complex functions to creating an entirely new language syntax in the interest of expressiveness. This expressiveness may come at the price of a higher barrier to entry, but once mastered, the precise control provided by these structures will be sorely missed when returning to other programming languages. 

\end{multicols}
\newpage
%----------------------------------------------------------------------
% SECTION X: APENDIX
%----------------------------------------------------------------------
\section{Apendix}\label{sec:apendix}

\subsection{Macro Expansion} \label{sec:macro-expand}

\begin{lstlisting}
(macroexpand
 `(loop for i in `(1 2 3 4 5)
     do
     (print i)))
     
=> (MACROLET ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
 (BLOCK NIL
  (LET ((#:LIST-9518 '(1 2 3 4 5)))
   (PROGN
    (LET ((I NIL))
     (LET NIL
      (MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
       (TAGBODY SYSTEM::BEGIN-LOOP (WHEN (ENDP #:LIST-9518) (LOOP-FINISH))
        (SETQ I (CAR #:LIST-9518)) (PROGN (PROGN (PRINT I)))
        (PSETQ #:LIST-9518 (CDR #:LIST-9518)) (GO SYSTEM::BEGIN-LOOP)
        SYSTEM::END-LOOP
        (MACROLET
         ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN)
           '(GO SYSTEM::END-LOOP)))))))))))) 
\end{lstlisting}


\subsection{Maximal Sum Contiguous Subsequence Problem}

\begin{lstlisting}
; define a helper class that represents a sub-sequence
; within this context with sum book keeping.
(defclass sub-sequence ()
  ((sum :initform 0
	:initarg :sum
	:accessor get-sum
	:type number
	:documentation "The sum of this sequence")
   (sequence :initform nil
	     :initarg :sub-sequence
	     :accessor get-sequence
	     :type list
	     :documentation "The sub-sequence")))

(defmethod get-sum ( (s sequence) )
  (slot-value s `sum))

(defmethod get-sequence ( (s sequence) )
  (slot-value s `sequence))

; helper function to slice a list
(defun sublist (start end l)
  (set-difference (nthcdr start l) (nthcdr (+ end 1) l)))


; generate the maximal sum contiguous subsequence and its
; sum and return it in a sub-sequence object defined above
(defun max-sum-subsequence (seq)
  
  (let ((maxsofar 0) 
	(maxendinghere 0)
	(i 0) 
	(start-index 0)
	(end-index 0)
	(rseq (make-instance `sub-sequence)))
    (loop for s in seq
       do
	 (setf maxendinghere (max (+ maxendinghere s) 0))
	 
	 ;store the start index of the sub sequence
	 (if (eql maxendinghere 0)
	     (setf start-index (+ i 1)))
	 
	 ;store the end index of the sub sequence
	 (if (> maxendinghere maxsofar)
	     (setf end-index i))
	 
	 (setf maxsofar (max maxsofar maxendinghere))
	 
	 (setf i (+ i 1)))
    (setf (get-sequence rseq) (sublist start-index end-index seq))
    (setf (get-sum rseq) maxsofar)
    rseq))
    
SEQUENCE: (31 -41 59 26 -53 58 97 -93 -23 84)
MAX SUBSEQUENCE: (59 26 -53 58 97) = 187

SEQUENCE: (1 2 -3 -4 5 6 7 44 22 -2 4 -66 33)
MAX SUBSEQUENCE: (5 6 7 44 22 -2 4) = 86

SEQUENCE: (11 -5 6 -77 9 14 -5 -2 -1 4)
MAX SUBSEQUENCE: (9 14) = 23

SEQUENCE: (55 99 -111 83 1 4 5 6 -3 -6 -7 3 5 -6 -32 44 5 12 3 -150)
MAX SUBSEQUENCE: (55 99 -111 83 1 4 5 6 -3 -6 -7 3 5 -6 -32 44 5 12 3) = 160
\end{lstlisting}

%----------------------------------------------------------------------
% SECTION X: Bibliography
%----------------------------------------------------------------------

\newpage
\thispagestyle{empty}
\begin{thebibliography}{1}
\bibliographystyle{IEEEbib}
\bibliography{bibliography}
\end{thebibliography}

\end{document}









